
/*
 * @Author: lijing
 * @e-mail: 1413979079@qq.com
 * @LastEditors: lijing
 * @Date: 2019-11-08 21:30:46
 * @LastEditTime: 2019-11-08 22:32:21
 * @FilePath: \InversePairs\Sort.java
 * @Description: 归并排序
 */
import java.util.Arrays;

public class Sort {
  public static void sort(int[] arr) {
    sort(arr, 0, arr.length - 1);
  }

  public static void sort(int[] arr, int l, int r) {
    if (l == r) {
      return;
    }
    int mid = l + ((r - l) >> 1);
    sort(arr, l, mid);
    sort(arr, mid + 1, r);
    merge(arr, l, r, mid);
  }

  /**
   * 合并两个有序数组
   * 
   * @param arr1
   * @param arr2
   * @return
   */
  public static void merge(int[] arr, int l, int r, int mid) {
    int[] temp = new int[r - l + 1];
    int i = 0;
    int p1 = l;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= r) {
      if (arr[p1] < arr[p2]) {
        temp[i++] = arr[p1++];
      } else {
        temp[i++] = arr[p2++];
      }

    }
    while (p1 <= mid) {
      temp[i++] = arr[p1++];
    }
    while (p2 <= r) {
      temp[i++] = arr[p2++];
    }
    i = 0;
    for (int j = l; j <= r; j++) {
      arr[j] = temp[i++];
    }
    System.out.println(Arrays.toString(arr));
  }

  public static void main(String[] args) {
    int[] arr = new int[] { 4, 3, 2, 7, 6, 5, 1, 8, 7, 9 };
    sort(arr);
    System.out.println(Arrays.toString(arr));
  }
}